package 数据结构.链表;

/**
 * @author Veng Su 1344114844@qq.com
 * @date 2018/7/17 16:22
 */
public class LinkedList<E> {
    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    '}';
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedList() {
        dummyHead = new Node(null, null);
        size = 0;
    }

    /**
     * 获取链表中的个数
     */
    public int getSize() {
        return size;
    }

    /**
     * 链表是否为空
     *
     * @return true，则链表为空，false链表不为空
     */
    public boolean isEmpty() {
        return size == 0;
    }



    /**
     * 向链表中某个位置插入结点
     * index 从0开始
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index: require >0&&<=size");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
//            Node node = new Node(e);
//            node.next = prev.next;
//            prev.next = node;
        prev.next = new Node(e, prev.next);

        size++;
    }

    /**
     * 向链表末尾添加结点
     *
     * @param e 结点的值
     */
    public void addLast(E e) {
        add(size, e);
    }
    /**
     * 在链表头添加新的元素
     *
     * @param e 结点的值
     */
    public void addFirst(E e) {
        add(0,e);
    }

    /**
     * 获取指定位置的结点
     * @param index 指定位置，从0开始
     * @return E 结点的值
     */
    public E get(int index){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index: require >0&&<size");
        }
        Node node=dummyHead.next;
        for (int i = 0; i < index; i++) {
            node=node.next;
        }
        return node.e;
    }

    public E getFirst(){
        return get(0);
    }
    public E getLast(){
        return get(size-1);
    }

    /**
     * 修改某个位置的结点的值
     * @param index 某个位置
     * @param e 结点的值
     */
    public void set(int index,E e){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index: require >0&&<size");
        }
        Node cur=dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur=cur.next;
        }
        cur.e=e;
    }

    /**
     * 查找链表中的值是否有e的值
     * @param e 结点的值
     * @return true，有这个值，false 没有这个值
     */
    public boolean contains(E e){
        Node cur=dummyHead.next;
        while (cur!=null){
            if (cur.e.equals(e)){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }


    /**
     * 删除指定位置的结点
     * @param index 指定位置
     * @return 结点的值
     */
    public E remove(int index){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index: require >0&&<size");
        }
        Node prev=dummyHead;
        for (int i = 0; i < index; i++) {
            prev=prev.next;
        }
        Node ret=prev.next;
        prev.next=ret.next;
        ret.next=null;
        size--;
        return ret.e;
    }
    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size-1);
    }
    public void removeElement(E e){
        if (dummyHead.next==null){
            throw new  IllegalArgumentException("链表为空");
        }
        Node prev=dummyHead;
        while (prev.next!=null){
            if (prev.next.e.equals(e)){
                Node ret=prev.next;
                prev.next=ret.next;
                ret.next=null;
            }else {
                prev=prev.next;
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder res=new StringBuilder();
        Node cur=dummyHead.next;
        while (cur!=null){
            res.append(cur).append("->");
            cur=cur.next;
        }
        res.append("null");
        return res.toString();
    }
}
